package com.taotao.linklist;

import lombok.Getter;
import lombok.Setter;

import java.util.Arrays;
import java.util.List;

/**
 * 类描述
 *
 * @author Administrator
 * @date 2020/7/11 23:37
 */
public class CheckLoop {

    @Getter
    @Setter
    public static class Node<T> {
        T data;
        Node<T> next;
    }

    /**
     * 检查是否有环
     *
     * @param head
     * @param <T>
     * @return
     */
    public static <T> boolean checkLoop(Node<T> head) {
        Node<T> fastP = head;
        Node<T> slowP = head;

        while (null != fastP && null != fastP.next){
            fastP = fastP.next.next;
            slowP = slowP.next;

            if(slowP == fastP){
                return true;
            }
        }

        return false;
    }


    /**
     * 创建链表
     *
     * @param <T>
     * @return
     */
    public static <T> Node<T> createLinkList(List<T> datas) {
        Node<T> head = new Node<>();
        if (null == datas || 0 == datas.size()) {
            return head;
        }

        Node<T> lastNode = head;
        for(T d:datas){
            Node<T> node = new Node<>();
            node.setData(d);
            lastNode.next = node;
        }


        return head;
    }

    /**
     *
     * 在链表中创建环
     *
     * @param head
     * @param n 环在第n个节点
     * @param <T>
     */
    public static <T> void createLoop(Node<T> head,int n){
        Node<T> lastNode = head;
        Node<T> nodeN = head;

        int i = 0;
        while(null != lastNode && i < n){
            lastNode = lastNode.next;
            nodeN = nodeN.next;
            i++;
        }

        while(null != lastNode ){
            lastNode = lastNode.next;
        }


        lastNode.next = nodeN;

    }



    public static void main(String[] args) {

        List<String>  list = Arrays.asList("a","b","c","d","e","f","g","h","i");

        Node<String> head =createLinkList(list);

        createLoop(head,4);

        System.out.println(checkLoop(head));



    }
}
